package com.leetcode.根据数据结构分类.图;


import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2021/1/12
 * @description: 207. 课程表
 * https://leetcode-cn.com/problems/course-schedule/
 */
public class B_207_课程表 {

    /**
     * 分析起来其实这就是一个图的拓扑排序以及判断是否在拓扑排序中存在环的问题！
     * 但是，如何仅仅用 数组/列表 来表示图呢？
     * --
     * 这个题目似乎还用不着特别的抽象
     * 使用 Kahn 算法实现拓扑排序。
     * {@link com.sourcetrip.algorithm.graph.AdjacencyListGraphV0#topologicalSortByKahn(List)}
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Queue<Integer> queue = new LinkedList<Integer>();
        //HashMap<Integer, Integer> table = new HashMap<>();
        //建立一个数组记录 numCourses 的入度
        int[] array = new int[numCourses];
        //记录每一个课程的出度
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            int to = prerequisites[i][1];
            array[to]++;
            int from = prerequisites[i][0];
            if (map.containsKey(from)) {
                map.get(from).add(to);
            } else {
                ArrayList<Integer> integers = new ArrayList<>();
                integers.add(to);
                map.put(from, integers);
            }
        }
        //找到 入度 = 0
        for (int i = 0; i < numCourses; i++) {
            if (array[i] == 0) {
                queue.offer(i);
            }
        }
        int count = 0;
        while (!queue.isEmpty()) {
            //当前课程的索引
            Integer cur = queue.poll();
            count++;
            //拿到出度
            List<Integer> integers = map.get(cur);
            if (integers == null) {
                continue;
            }
            for (int i = 0; i < integers.size(); i++) {
                if (--array[integers.get(i)] == 0) {
                    queue.offer(integers.get(i));
                }

            }
        }
        return count == numCourses;
    }

    public static void main(String[] args) {
        int numCourses = 2;
//        int[][] prerequisites = {{1, 0}};
//        int[][] prerequisites = {{1, 0}, {0, 1}};
        int[][] prerequisites = {{0, 1}};
        B_207_课程表 action = new B_207_课程表();
        boolean b = action.canFinish(numCourses, prerequisites);
        System.out.println("b = " + b);
    }
}
